#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2019年10月26日
版    本：v1.0.0
描    述：
Copyright (C) 2019 All rights reserved.
'''


class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        houses.sort()
        heaters.sort()

        max_radius = 0
        index = 0
        for c in houses:
            start = index
            end = len(heaters)-1
            while start < end:
                mid = (end - start)//2 + start
                if c == heaters[mid]:
                    start = mid
                    break
                elif heaters[mid] < c:
                    start = mid+1
                else:
                    end = mid

            if c == heaters[start]:
                continue
            elif heaters[start] < c:
                max_radius = max(c - heaters[start], max_radius)
            elif start > 0:
                tmp = min(heaters[start] - c, c - heaters[start-1])
                max_radius = max(tmp, max_radius)
            else:
                max_radius = max(heaters[start] - c, max_radius)

        return max_radius
